package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

var (
	sc = &myScanner{bufio.NewScanner(os.Stdin)}
	wr = &myWriter{bufio.NewWriter(os.Stdout)}
)

// 解答欄
func solve() {

}

func main() {
	startBufSize := 4096
	maxBufSize := math.MaxInt64
	sc.Buffer(make([]byte, startBufSize), maxBufSize)
	sc.Split(bufio.ScanWords)
	solve()
	wr.Flush()
}

func arr3(n, m, k int) [][][]int {
	res := make([][][]int, n)
	for i := 0; i < n; i++ {
		res[i] = make([][]int, m)
		for j := 0; j < m; j++ {
			res[i][j] = make([]int, k)
		}
	}
	return res
}

func arr2(n, m int) [][]int {
	res := make([][]int, n)
	for i := 0; i < n; i++ {
		res[i] = make([]int, m)
	}
	return res
}

func arr1(n int) []int {
	res := make([]int, n)
	return res
}

// useful funcs for slice
func makeInts(n, x int) []int {
	res := make([]int, n)
	for i := range res {
		res[i] = x
	}
	return res
}
func makeBools(n int, b bool) []bool {
	res := make([]bool, n)
	for i := range res {
		res[i] = b
	}
	return res
}
func countTrue(bs []bool) int {
	res := 0
	for _, b := range bs {
		if b {
			res++
		}
	}
	return res
}

// input
type myScanner struct {
	*bufio.Scanner
}

func lii(n int) []int {
	return sc.getInts(n)
}

func ii() int {
	return sc.getInt()
}

func i() string {
	return sc.getString()
}

func na(n int) []string {
	return sc.getStrings(n)
}

func (sc *myScanner) getInt() int {
	return sc._getIntOffset(0)
}
func (sc *myScanner) getInt2() (int, int) {
	return sc.getInt(), sc.getInt()
}
func (sc *myScanner) getInt3() (int, int, int) {
	return sc.getInt(), sc.getInt(), sc.getInt()
}
func (sc *myScanner) getInt4() (int, int, int, int) {
	return sc.getInt(), sc.getInt(), sc.getInt(), sc.getInt()
}
func (sc *myScanner) getInts(n int) []int {
	return sc._getIntsOffset(n, 0)
}
func (sc *myScanner) getIntZeroIndexed() int {
	return sc._getIntOffset(-1)
}
func (sc *myScanner) getIntsZeroIndexed(n int) []int {
	return sc._getIntsOffset(n, -1)
}
func (sc *myScanner) _getIntOffset(x int) int {
	res, err := strconv.Atoi(sc.getString())
	if err != nil {
		panic(err)
	}
	return res + x
}
func (sc *myScanner) _getIntsOffset(n, x int) []int {
	res := make([]int, n)
	for i := range res {
		res[i] = sc._getIntOffset(x)
	}
	return res
}
func (sc *myScanner) getString() string {
	sc.Scan()
	return sc.Text()
}
func (sc *myScanner) getStrings(n int) []string {
	res := make([]string, n)
	for i := range res {
		res[i] = sc.getString()
	}
	return res
}
func (sc *myScanner) getRunes() []rune {
	return []rune(sc.getString())
}
func (sc *myScanner) getFloat() float64 {
	res, err := strconv.ParseFloat(sc.getString(), 64)
	if err != nil {
		panic(err)
	}
	return res
}
func (sc *myScanner) getFloats(n int) []float64 {
	res := make([]float64, n)
	for i := range res {
		res[i] = sc.getFloat()
	}
	return res
}

// output
type myWriter struct {
	*bufio.Writer
}

func (wr *myWriter) println(a ...interface{}) {
	fmt.Fprintln(wr, a...)
}
func (wr *myWriter) printf(format string, a ...interface{}) {
	fmt.Fprintf(wr, format, a...)
}

// simple math funcs for int
func max(as ...int) int {
	res := as[0]
	for _, a := range as {
		if res < a {
			res = a
		}
	}
	return res
}
func min(as ...int) int {
	res := as[0]
	for _, a := range as {
		if res > a {
			res = a
		}
	}
	return res
}
func chMax(a *int, b int) {
	*a = max(*a, b)
}

func chMin(a *int, b int) {
	*a = min(*a, b)
}
func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}
func pow(a, n int) int {
	res := 1
	b := a
	for n > 0 {
		if n&1 > 0 {
			res *= b
		}
		n >>= 1
		b *= b
	}
	return res
}
func sum(s ...int) int {
	res := 0
	for _, v := range s {
		res += v
	}
	return res
}
func checkPrime(a int) bool {
	if a == 2 {
		return true
	} else if a%2 == 0 {
		return false
	}
	res := true
	for q := 3; q*q <= a; q += 2 {
		if a%q == 0 {
			res = false
			break
		}
	}
	return res
}

type DefaultdictList struct {
	mp map[interface{}][]interface{}
}

func NewDefaultdictList() *DefaultdictList {
	return &DefaultdictList{make(map[interface{}][]interface{})}
}

func (dict *DefaultdictList) Append(k, v interface{}) {
	if _, ok := dict.mp[k]; !ok {
		dict.mp[k] = []interface{}{}
	}
	dict.mp[k] = append(dict.mp[k], v)
}

func (dict *DefaultdictList) Get(k interface{}) []interface{} {
	return dict.mp[k]
}

func (dict *DefaultdictList) Len() int {
	return len(dict.mp)
}
